package com.gxc.sort;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给一个包含n个整数元素的集合a，一个包含m个整数元素的集合b。
 * 定义magic操作为，从一个集合中取出一个元素，放到另一个集合里，且操作过后每个集合的平均值都大大于于操作前。
 * 注意以下两点:
 * 	1)不可以把一个集合的元素取空，这样就没有平均值了
 * 	2)值为x的元素从集合b取出放入集合a，但集合a中已经有值为x的元素，则a的平均值不变(因为集合元素不会重复)，b的平均值可能会改变(因为x被取出了）
 * 问最多可以进行多少次magic操作?
 *
 * magic后每个集合的平均值都大于操作前，
 * 只能从大平均值的集合往小平均值的集合移动元素，元素的大小要小于大平均值，大于小平均值
 */
public class Magic {

    public static void main(String[] args) {
        int[] a = new int[]{2};
        int[] b = new int[]{4, 3,5, 1, 1};

        System.out.println(magic(a, b));

        int i = 2;
        if (i-- == 1) {
            System.out.println("先比较再减减");
        }
        System.out.println(i);
    }

    public static int magic(int[] a, int[] b) {
        if (a == null || b == null) return 0;
        //求a的平均值
        double sum1 = 0;
        for (int i = 0; i < a.length; i++) {
            sum1 += a[i];
        }
        //求b的平均值
        double sum2 = 0;
        for (int i = 0; i < b.length; i++) {
            sum2 += b[i];
        }
        //如果两个集合的平均值相等，则不能移动
        if (avg(sum1, a.length) == avg(sum2,b.length)) return 0;

        int[] small = a;
        int[] big = b;
        double smallSum = sum1;
        double bigSum = sum2;
        int smallSize = a.length;
        int bigSize = b.length;
        if (avg(sum1, a.length) > avg(sum2,b.length)) {
            small = b;
            big = a;
            smallSum = sum2;
            bigSum = sum1;
            smallSize = b.length;
            bigSize = a.length;
        }

        //大集合元素的大小要小于大平均值，大于小平均值，然后从小到大往小集合移动
        Arrays.sort(big);
        //需要保持小集合的元素不重复
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < small.length; i++) {
            set.add(small[i]);
        }
        //最多可以进行多少次
        int time = 0;
        for (int i = 0; i < big.length-1; i++) {
            double cur = (double) big[i];
            if (cur>avg(smallSum, smallSize) && cur<avg(bigSum, bigSize) && !set.contains(big[i])) {
                //次数加1
                time++;
                //新加入的元素加入集合，保持小集合的元素不重复
                set.add(big[i]);
                smallSum += big[i];
                smallSize ++;

                bigSum -= big[i];
                bigSize --;
            }
        }

        return time;
    }

    public static double avg(double sum, int size) {
        return sum/(double) size;
    }
}
